package org.xingole.daily;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.com/problems/find-x-sum-of-all-k-long-subarrays-i/">
 * 3318 Problem Description
 * </a>
 * 
 * @since 2025-11-4
 */
public class FindXSumOfAllKLongSubarraysI {
    public int[] findXSum(int[] nums, int k, int x) {
        /*
         * The x-sum of an array is calculated by the following procedure:
         * 
         * 1. Count the occurrence of all elements in the array.
         * 2. Keep only the ocurrences of the top x most frequency elements. If two
         * elements have the same number of occurrences, the element with the bigger
         * value is considered more frequent.
         * 3. Calculate the sum of the resulting array.
         * 
         * Approach: Hash Table + Sorting
         * 
         * We enumerate all subarrays of length k, using a hash table cnt to count the 
         * occurrences of each number within the subarray. For each key-value pair
         * (key, value) in the hash table - where key represents a number and value
         * represents its occurrence count - we store them in an array and sort this
         * array primarily in descending order by value, and secondarily in descending
         * order by key.
         * 
         * After sorting, the first x tuples correspond to the x most frequent elements
         * and their counts.
         */

        int n     = nums.length;
        int[] ans = new int[n - k + 1];

        for (int i = 0; i < n - k; ++i) {
            Map<Integer, Integer> cnt = new HashMap<>();
            for (int j = i; j < i + k; ++j) {
                cnt.put(nums[j], cnt.getOrDefault(nums[j], 0) + 1);
            }

            List<int[]> freq = new ArrayList<>();
            for (var entry : cnt.entrySet()) {
                freq.add(new int[] { entry.getValue(), entry.getKey() });
            }

            freq.sort((a, b) -> b[0] != a[0] ? b[0] - a[0] : b[1] - a[1]);
            int xsum = 0;
            for (int j = 0; j < x && j < freq.size(); ++j) {
                xsum += freq.get(j)[0] * freq.get(j)[1];
            }
            ans[i]  = xsum;
        }

        return ans;
    }
}
